package com.datastructures2.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * @author MaoLin Wang
 * @date 2020/2/1815:34
 */
public class ShellSort {
    public static  void shellSort(int[] arr){
      int j;
        for (int gap = arr.length/2; gap >0 ; gap/=2) {
            for (int i = gap; i < arr.length; i++) {
                int temp=arr[i];
                for (j = i;  j-gap>=0 && temp<arr[j-gap];j--) {
                    arr[j]=arr[j-gap];
                }
                arr[j]=temp;

            }
        }

    }

    public static <T extends Comparable<? super T>>void  test(T[] arr){

       int j;
        for (int gap = arr.length/2; gap >=1 ; gap/=2) {

            for (int i = gap; i <arr.length ; i++) {

                T temp=arr[i];

                for (j = i;j-gap>=0 && temp.compareTo(arr[j-gap])<0 ; j-=gap) {
                    arr[j]=arr[j-gap];
                }
                arr[j]=temp;
            }

        }

    }
    public static void main(String[] args) {
        /*int [] arr=new int[3000000];
        Random random=new Random();
        for (int i = 0; i < 3000000; i++) {
            arr[i]=random.nextInt(3000000);
        }
        System.out.println("2");
        long s = System.currentTimeMillis();
        shellSort(arr);
        long f = System.currentTimeMillis();
        System.out.println(f-s);
*/
        Integer[]arr={45,12,21,4,425,12,14,5,5};
        test(arr);
        Arrays.stream(arr).forEach(num-> System.out.println(num));
    }
}
